package Top200;

/**
 * @author zhangmin
 * @create 2022-02-27 15:40
 */
public class numTrees96 {
    int[][] memo;
    int count(int left,int right){
        if (left>right){
            //null也是一种子树
            return 1;
        }
        if (memo[left][right] !=0){
            return memo[left][right];
        }
        int count=0;
        for (int i = left; i <= right; i++) {
            count+=count(left,i-1)*count(i+1,right);
        }
        memo[left][right] =count;
        return count;
    }

    public int numTrees(int n) {
        memo=new int[n+1][n+1];
        return count(1,n);
    }
}
